//采药 01背包
#include <iostream>
using namespace std;
const int MAXT=1000;
const int MAXM=100;
int t,m;
int w[MAXM+1],c[MAXM+1];
int maxc[MAXT+1];

int main(){
    cin>>t>>m;
    for(int i=1;i<=m;i++) cin>>w[i]>>c[i];

    for(int i=1;i<=m;i++)
        for(int v=t;v>=w[i];v--)
            if (maxc[v]<maxc[v-w[i]]+c[i]) 
                maxc[v]=maxc[v-w[i]]+c[i];
    cout<<maxc[t];
}